模拟，注意最后答案要减一。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public static void solve() {
int n = io.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = io.nextInt();
}
int b = 1;
for (int i = 0; i < n; i++) {
if (b == a[i]) b += 2;
else b += 1;
}
io.println(b - 1);
}
|
比赛时写复杂了，就是枚举不选哪个数，使用位运算会很简单。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| public static void solve() {
int n = io.nextInt();
long xor = 0L;
long[] s = new long[n];
for (int i = 0; i < n; i++) {
int k = io.nextInt();
for (int j = 0; j < k; j++) {
s[i] |= 1L << io.nextInt();
}
xor |= s[i];
}
int ans = 0;
for (int i = 1; i <= 50; i++) {
if ((xor >> i & 1) != 1) continue;
long res = 0L;
for (int j = 0; j < n; j++) {
if ((s[j] >> i & 1) != 1) {
res |= s[j];
}
}
ans = Math.max(ans, Long.bitCount(res));
}
io.println(ans);
}
|
思维题，没想出来。不管前两张牌如何操作，都必定可以拿到之后的所有正数牌，然后对前两张牌分类讨论即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
| public static void solve() {
int n = io.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = io.nextInt();
}
long ans = 0L;
for (int i = 2; i < n; i++) {
ans += Math.max(0, a[i]);
}
ans += Math.max(0, a[0] + Math.max(0, n > 1 ? a[1] : 0));
io.println(ans);
}
|
很典的换根 DP，因为第三题花费太长时间，导致差几分钟 AC。只要相邻的两个节点值不相同，它们就需要做一次操作。先以一个节点为根做 DFS，并记录所有节点的子树大小，和以该节点为根的成本。然后再做一次 DFS，换根计算代价的差值。（比赛时犯蠢，在换根的过程中打印答案，但是遍历不能保证从 \(1\) 到 \(n\) 的顺序，所以是错的）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| private static long[] ans;
private static int[] value, sz;
private static List<Integer>[] g;
public static void solve() {
int n = io.nextInt();
value = new int[n];
for (int i = 0; i < n; i++) {
value[i] = io.nextInt();
}
g = new List[n];
Arrays.setAll(g, k -> new ArrayList<>());
for (int i = 0; i < n - 1; i++) {
int u = io.nextInt() - 1, v = io.nextInt() - 1;
g[u].add(v);
g[v].add(u);
}
sz = new int[n];
ans = new long[n];
dfs1(0, -1);
dfs2(0, -1);
for (int i = 0; i < n; i++) {
io.print(ans[i] + " ");
}
io.println();
}
private static void dfs1(int x, int fa) {
sz[x] = 1;
for (int y : g[x]) {
if (y == fa) continue;
dfs1(y, x);
sz[x] += sz[y];
ans[0] += (long) sz[y] * (value[x] ^ value[y]);
}
}
private static void dfs2(int x, int fa) {
for (int y : g[x]) {
if (y == fa) continue;
ans[y] = ans[x] + (long) (sz[0] - sz[y] - sz[y]) * (value[x] ^ value[y]);
dfs2(y, x);
}
}
|